class Solution {
public:
    int integerBreak(int n) {
        vector<int> res(n+1,0);
        for(int i=2;i<=n;i++){
            for(int j=1;j<i;j++){
                res[i]=max(max((i-j)*j,(i-j)*res[j]),res[i]);
                //cout<<"i:"<<i<<",j:"<<j<<",res["<<i<<"]:"<<res[i]<<endl;
            }
            //cout<<res[i]<<endl;
            //cout<<endl;
        }
        return res[n];
    }
};